/*
 * @lc app=leetcode.cn id=1020 lang=cpp
 *
 * [1020] 飞地的数量
 *
 * https://leetcode.cn/problems/number-of-enclaves/description/
 *
 * algorithms
 * Medium (61.89%)
 * Likes:    259
 * Dislikes: 0
 * Total Accepted:    72.8K
 * Total Submissions: 117.7K
 * Testcase Example:  '[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]'
 *
 * 给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
 * 
 * 一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
 * 
 * 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
 * 输出：3
 * 解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
 * 输出：0
 * 解释：所有 1 都在边界上或可以到达边界。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 500
 * grid[i][j] 的值为 0 或 1
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    bool DFS(vector<vector<int>>& grid, int r, int c, int& total) {
        if ((r < 0 || r >= grid.size()) || 
            (c < 0 || c >= grid[0].size()))
            return true;
        
        if (grid[r][c] == 0)
            return false;

        bool isNotEnclaves = false;
        grid[r][c] = 0;
        total++;


        //注意! 
        //DFS 要写在前面!!
        //否则会被 || 判断符号截断, 导致无法完全深度搜索
        isNotEnclaves = DFS(grid, r + 1, c, total) || isNotEnclaves;
        isNotEnclaves = DFS(grid, r, c + 1, total) || isNotEnclaves;
        isNotEnclaves = DFS(grid, r - 1, c, total) || isNotEnclaves;
        isNotEnclaves = DFS(grid, r, c - 1, total) || isNotEnclaves;

        return isNotEnclaves;
    }

    int numEnclaves(vector<vector<int>>& grid) {
        int total = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 0)
                    continue;

                int result = 0;
                if(!DFS(grid, i, j, result)) {
                    total += result;
                }
            }
        }

        return total;
    }
};
// @lc code=end

